package codingforgreat.class47;


import java.util.Arrays;
import java.util.HashMap;

/**
 * 题目描述:
 * 一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易，表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学（0, 1, 2 为人的标号），上述交易可以表示为 [[0, 1, 10], [2, 0, 5]]。
 *
 * 给定一群人之间的交易信息列表，计算能够还清所有债务的最小次数。
 *
 * 注意：
 *
 * 一次交易会以三元组 (x, y, z) 表示，并有 x ≠ y 且 z > 0。
 *
 * 人的标号可能不是按顺序的，例如标号可能为 0, 1, 2 也可能为 0, 2, 6。
 *
 * 示例:
 * 示例 1：
 *
 * 输入：
 * [[0,1,10], [2,0,5]]
 * 输出：
 * 2
 * 解释：
 * 人 #0 给人 #1 共计 10 美元。
 * 人 #2 给人 #0 共计 5 美元。
 * 需要两次交易。一种方式是人 #1 分别给人 #0 和人 #2 各 5 美元。
 * 示例 2：
 *
 * 输入：
 * [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
 * 输出：
 * 1
 * 解释：
 * 人 #0 给人 #1 共计 10 美元。Person #0 gave person #1 $10.
 * 人 #1 给人 #0 共计 1 美元。Person #1 gave person #0 $1.
 * 人 #1 给人 #2 共计 5 美元。Person #1 gave person #2 $5.
 * 人 #2 给人 #0 共计 5 美元。Person #2 gave person #0 $5.
 * 因此，人 #1 需要给人 #0 共计 4 美元，所有的债务即可还清。
 * */
public class Problem_0465_OptimalAccountBalancing {

    public static int minTransfers1(int[][] transactions) {
        int[] debts = getDebts(transactions);
        int N = debts.length;
        return N - process(debts,(1 << N) - 1,0,N);
    }
    public static int process(int[] debts,int set,int sum,int N){
        if((set & (set - 1)) == 0){
            return 0;
        }
        int value = 0;
        int max = 0;
        for(int i = 0;i < N;i++){
            value = debts[i];
            if((set & (1 << i)) != 0){
                max = Math.max(max,process(debts,set - (1 << i),sum + value,N));
            }
        }
        return sum == 0 ? max + 1 : max;
    }
    public static int[] getDebts(int[][] trans){
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int[] tran : trans){
            map.put(tran[0], map.getOrDefault(tran[0], 0) + tran[2]);
            map.put(tran[1], map.getOrDefault(tran[1], 0) - tran[2]);
        }
        int N = 0;
        for(int v : map.values()){
            if(v != 0){
                N++;
            }
        }
        int[] res = new int[N];
        int index = 0;
        for (int value : map.values()) {
            if (value != 0) {
                res[index++] = value;
            }
        }
        return res;
    }


    // 上面的尝试过程 + 记忆化搜索
    // 最优解
    public static int minTransfers2(int[][] transactions) {
        int[] debt = debts(transactions);
        int N = debt.length;
        int sum = 0;
        for (int num : debt) {
            sum += num;
        }
        int[] dp = new int[1 << N];
        Arrays.fill(dp, -1);
        return N - process2(debt, (1 << N) - 1, sum, N, dp);
    }

    public static int process2(int[] debt, int set, int sum, int N, int[] dp) {
        if (dp[set] != -1) {
            return dp[set];
        }
        int ans = 0;
        if ((set & (set - 1)) != 0) {
            int value = 0;
            int max = 0;
            for (int i = 0; i < N; i++) {
                value = debt[i];
                if ((set & (1 << i)) != 0) {
                    max = Math.max(max, process2(debt, set ^ (1 << i), sum - value, N, dp));
                }
            }
            ans = sum == 0 ? max + 1 : max;
        }
        dp[set] = ans;
        return ans;
    }

    public static int[] debts(int[][] transactions) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int[] tran : transactions) {
            map.put(tran[0], map.getOrDefault(tran[0], 0) + tran[2]);
            map.put(tran[1], map.getOrDefault(tran[1], 0) - tran[2]);
        }
        int N = 0;
        for (int value : map.values()) {
            if (value != 0) {
                N++;
            }
        }
        int[] debt = new int[N];
        int index = 0;
        for (int value : map.values()) {
            if (value != 0) {
                debt[index++] = value;
            }
        }
        return debt;
    }

    // 为了测试
    public static int[][] randomTrans(int s, int n, int m) {
        int[][] trans = new int[s][3];
        for (int i = 0; i < s; i++) {
            trans[i][0] = (int) (Math.random() * n);
            trans[i][1] = (int) (Math.random() * n);
            trans[i][2] = (int) (Math.random() * m) + 1;
        }
        return trans;
    }

    // 为了测试
    public static void main(String[] args) {
        int s = 8;
        int n = 8;
        int m = 10;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[][] trans = randomTrans(s, n, m);
            int ans1 = minTransfers1(trans);
            int ans2 = minTransfers2(trans);
            if (ans1 != ans2) {
                System.out.println("Oops!");
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }
        System.out.println("测试结束");
    }
}
